Coloração de arestas

3-coloração-de-arestas do grafo de Desargues.

Em teoria dos grafos, uma coloração de arestas de um grafo é a atribuição de “cores” para as arestas de um grafo de forma que não haja duas arestas adjacentes tendo a mesma cor. Por exemplo, a figura à direita mostra uma coloração de arestas de um grafo com as cores vermelha, azul e verde. Coloração de arestas é um dos vários tipos de coloração de grafos.

O Problema da coloração de arestas pergunta se é possível colorir um dado grafo usando no máximo n cores. O número mínimo exigido de cores para um grafo é chamado de índice cromático. Por exemplo, o grafo à direita pode ser colorido com três cores, mas não pode ser colorido por duas cores, e, portanto, tem o índice cromático três.

Definição

Tal como acontece com a sua contrapartida em vértices, uma coloração de arestas de um grafo, quando mencionada sem qualquer qualificação, é sempre assumida ser uma coloração própria das arestas, significando que não há duas arestas adjacentes atribuídas com a mesma cor. Aqui, "adjacentes" significa não compartilhar um mesmo vértice. Uma coloração própria com k cores é chamada uma k-aresta-coloração (própria) e é equivalente ao problema de particionamento do conjunto de arestas em k acoplamentos. A um grafo que pode ser atribuída uma (própria) k-arestas-coloração é k-aresta-colorível. Uma 3-arestas-coloração de um grafo cúbico é algumas vezes chamada uma coloração Tait.

O menor número de cores necessárias em uma (própria) coloração de arestas de um grafo G é o índice cromático, ou número cromático de arestas, χ′(G), também, por vezes, simbolizado $\chi _{1}(G)$. Um grafo é k-arestas-cromático se o seu índice cromático é exatamente k. O índice cromático não deve ser confundido com o número cromático χ(G).

Propriedades

Em seguida, façamos Δ(G) denotar o grau máximo; e μ(G), a multiplicidade. Algumas propriedades de χ′(G):

1. χ′(G) = 1 se e somente se G é um acoplamento.
2. χ′(G) ≥ Δ(G).
3. χ′(G) ≤ Δ(G) + 1. (Teorema de Vizing, nomeado em honra a Vadim G. Vizing que o descobriu em 1964, divide todos os grafos em 2 classes: Classe 1 grafos tem χ′(G) = Δ(G); Classe 2 grafos tem χ′(G) = Δ(G)+1).
4. χ′(G) ≤ Δ(G) + μ(G), onde G é permitido ser um multigrafo.
5. χ′(G) ≤ (3/2)Δ(G) para qualquer multigrafo .
6. χ′(G) = Δ(G) se G é um grafo bipartido. (teorema bipartido de König)
7. χ′(G) = Δ(G) se G é simples, planar e Δ(G) ≥ 7. (Vizing,1965 combinado com Sanders e Zhao,2001)
8. χ′(G) = Δ(G) para quase todos os grafos (Erdős e Wilson, 1977).

Classificando grafos e encontrando seu índice cromático

Como podemos ver acima, χ′(G) é igual a Δ(G) ou Δ(G) + 1. Quando χ′(G) = Δ(G), G é dito ser Classe 1; caso contrário, Classe 2. (Holyer, 1981) provou que é NP-completo determinar se um grafo simples é Classe 1 ou Classe 2. No entanto, esforços têm sido feitos para dar uma caracterização parcial.

Por exemplo, Vizing (1965) mostrou que um grafo simples planar é da Classe 1, se o seu grau máximo é de pelo menos 8. Em contraste, ele observou que para os graus máximos 2, 3, 4, e 5, existem grafos planares simples da Classe 2. Por exemplo, comece com um sólido platônico e substitua uma única aresta por um caminho de duas arestas adjacentes. Desta forma, os sólidos platônicos resultam em simples grafos planares de classe 2 de grau máximo de 3, 4 e 5. (Cada ciclo de comprimento ímpar é um grafo de classe 2 de grau máximo 2).

Vizing conjecturou o seguinte resultado para os dois casos, que ele não resolveu:

Conjectura Vizing do grafo planar.

Todos os grafos simples e planares com grau máximo 6 ou 7 são de Classe 1.

Sanders & Zhao (2001) provaram parcialmente a conjectura do grafo planar de Vizing. Eles mostraram que todos os grafos simples e planares com grau máximo de 7 são da classe 1. Assim, o único caso que permanece sem solução de grafos simples e planares é o grau máximo de 6.

Esta conjectura tem implicações para a conjectura da coloração total